package com.itheima.search;

import java.util.Scanner;

public class A01demp1 {
    public static void main(String[] args) {
        //熟悉分块查找的思想
        //使用分块查找数据
        //第一个块的最大数据小于后一个块的所有数据
        int[] arr = {16, 5, 9, 12, 21, 18,
                32, 23, 37, 26, 45, 34,
                50, 48, 61, 52, 73, 66};

        //设定分块
        Block b1 = new Block(21, 0, 5);
        Block b2 = new Block(45, 6, 11);
        Block b3 = new Block(73, 12, 17);

        //定义一个数组存储表
        Block[] blockarr = {b1, b2, b3};

        //定义要查找的元素
        Scanner sc=new Scanner(System.in);
        System.out.println("请输入要从数组中查找的数据");
        int number = sc.nextInt();

        //定义方法调用方法  传递表 数组 要查找的元素
        int index = getIndex(blockarr, arr, number);
        System.out.println(index);
    }

    private static int getIndex(Block[] blockarr, int[] arr, int number) {
        //调用方法判断在那一个块中
        int indexBloclk = getIndexBloclk(blockarr, number);

        //number不在数组中
        if (indexBloclk == -1) {
            return -1;
        }

        //在数组中
        //定义起始索引 结束索引
        int startIndex = blockarr[indexBloclk].getStartIndex();
        int endIndex = blockarr[indexBloclk].getEndIndex();
        for (int i = startIndex; i <= endIndex; i++) {
            if (arr[i] == number) {
                return i;
            }
        }
        return -1;
    }

    //定义一个方法确定在哪一个块中
    public static int getIndexBloclk(Block[] blockarr, int number) {
//        Block b1=new Block(21,0,5);
//        Block b2=new Block(45,6,11);
//        Block b3=new Block(73,12,17);
        //进行遍历
        for (int i = 0; i < blockarr.length; i++) {
            if (number <= blockarr[i].getMax()) {
                return i;
            }
        }
        return -1;
    }
}

class Block {
    private int max;
    private int startIndex;
    private int endIndex;

    public Block() {
    }

    public Block(int max, int startIndex, int endIndex) {
        this.max = max;
        this.startIndex = startIndex;
        this.endIndex = endIndex;
    }

    public int getMax() {
        return max;
    }

    public void setMax(int max) {
        this.max = max;
    }

    public int getEndIndex() {
        return endIndex;
    }

    public void setEndIndex(int endIndex) {
        this.endIndex = endIndex;
    }

    public int getStartIndex() {
        return startIndex;
    }

    public void setStartIndex(int startIndex) {
        this.startIndex = startIndex;
    }
}
